{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Two Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两整数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>a</code> 和 <code>b</code> ，<strong>不使用 </strong>运算符&nbsp;<code>+</code> 和&nbsp;<code>-</code>&nbsp;​​​​​​​，计算并返回两整数之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 1, b = 2\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 2, b = 3\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-1000 &lt;= a, b &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-two-integers](https://leetcode.cn/problems/sum-of-two-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-two-integers](https://leetcode.cn/problems/sum-of-two-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2', '2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你两个正整数：n 和 target 。\n",
    "\n",
    "# 如果数组 nums 满足下述条件，则称其为 美丽数组 。\n",
    "\n",
    "\n",
    "# nums.length == n.\n",
    "# nums 由两两互不相同的正整数组成。\n",
    "# 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。\n",
    "# 返回符合条件的美丽数组所可能具备的 最小 和。\n",
    "class Solution:\n",
    "    def minimumPossibleSum(self, n: int, target: int) -> int:\n",
    "        def getSum(first: int, diff: int, count: int) -> int:\n",
    "            last = first + (count - 1) * diff\n",
    "            return (first + last) * count // 2\n",
    "\n",
    "        half = target // 2\n",
    "        if half >= n:\n",
    "            return getSum(1, 1, n)\n",
    "\n",
    "        return getSum(1, 1, half) + getSum(target, 1, n - half)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 ~ threshold\n",
    "    def getSum(self, nums: List[int], x: int) -> int:\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += math.ceil(num / x)\n",
    "        return sum\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.getSum(nums, mid) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 ~ threshold\n",
    "    def getSum(self, nums: List[int], x: int) -> int:\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += (num + x - 1) // x\n",
    "        return sum\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.getSum(nums, mid) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return sum([a,b])\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # a = a if a >= 0 else a + 2<<31\n",
    "        # b = b if b >= 0 else b + 2<<31\n",
    "        # while b:\n",
    "        #     a, b = a ^ b, (a & b) << 1\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \n",
    "        a +=b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        import ctypes\n",
    "        a = ctypes.c_int32(a).value\n",
    "        b = ctypes.c_int32(b).value\n",
    "        while b != 0:\n",
    "            carry = ctypes.c_int32(a & b).value\n",
    "            a = ctypes.c_int32(a ^ b).value\n",
    "            b = ctypes.c_int32(carry << 1).value\n",
    "\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return a+b\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: 'int', b: 'int') -> 'int':\n",
    "        while b != 0:              # 进位标志位\n",
    "            temp = a ^ b           # 利用异或（半加）运算来计算不带进位的加法结果，注意负数按位与需要先算补码再求回原码\n",
    "            b = (a & b) << 1       # 利用与运算计算进位的标志\n",
    "            a = temp & 0xFFFFFFFF  # 每次都把num1规定成一个32位的数\n",
    "        return a if a >> 31 == 0 else a - 4294967296"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        # if b == 0:\n",
    "        #     return a if a <= 0x80000000 else ~((a % 0x7fffffff) ^ 0x80000000)\n",
    "        # carry = ((a & b) << 1) % 0x100000000\n",
    "        # a = (a ^ b) % 0x100000000\n",
    "        # return self.getSum(a, carry)\n",
    "        mask=0x100000000\n",
    "        max_int=0x7fffffff\n",
    "        min_int=0x80000000\n",
    "        while b:\n",
    "            a,b=(a^b)%mask,((a&b)<<1)%mask\n",
    "        return a if a<=max_int else ~((a%min_int)^max_int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return sum([a,b])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getSum(self, a, b):\n",
    "        mask = 0x100000000\n",
    "        max_num = 0x7FFFFFFF\n",
    "        min_num = 0x80000000\n",
    "        while b != 0:\n",
    "            carry = (a & b) << 1\n",
    "            a = (a ^ b) % mask\n",
    "            b = carry % mask\n",
    "        return a if a < min_num else ~((a % min_num) ^ max_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return sum([a,b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return sum([a,b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "\n",
    "        a = a&0xFFFFFFFF\n",
    "        b = b&0xFFFFFFFF\n",
    "\n",
    "        s = a^b\n",
    "\n",
    "        while a&b != 0:\n",
    "            c = ((a&b)<<1)&0xFFFFFFFF\n",
    "            a = s\n",
    "            b = c \n",
    "            s = a^b\n",
    "\n",
    "        return s if s<0x80000000 else ~(s^0xFFFFFFFF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        # xor\n",
    "        # a^b为无进位加法\n",
    "        # (a & b) << 1 为进位\n",
    "        # 和=无进位加法+进位\n",
    "        # 如此循环，直到没有进位\n",
    "        MASK = 0x100000000\n",
    "        # 整型最大值\n",
    "        MAX_INT = 0x7FFFFFFF\n",
    "        MIN_INT = MAX_INT + 1\n",
    "        while b != 0:\n",
    "            # 计算进位\n",
    "            carry = (a & b) << 1 \n",
    "            # 取余范围限制在 [0, 2^32-1] 范围内\n",
    "            a = (a ^ b) % MASK\n",
    "            b = carry % MASK\n",
    "        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT) \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from ctypes import c_int32\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        mask = 0xffffffff\n",
    "        a &= mask\n",
    "        b &= mask\n",
    "        while b:\n",
    "            a, b = a^b, ((a&b) << 1) & mask\n",
    "        res = c_int32(a).value\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        a = a&0xFFFFFFFF\n",
    "        b = b&0xFFFFFFFF\n",
    "        while b != 0:\n",
    "            carry = a&b\n",
    "            a = a^b\n",
    "            b = (carry<<1)&0xFFFFFFFF\n",
    "        return a if a < 0x80000000 else ~(a^0xFFFFFFFF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        MASK2 = 2147483648  # 2^31\n",
    "        MASK3 = 2147483647  # 2^31-1\n",
    "        t = 0\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            u1 = (a >> i) & 1\n",
    "            u2 = (b >> i) & 1\n",
    "            if u1 & u2:\n",
    "                ans |= (t << i)\n",
    "                t = 1\n",
    "            elif u1 or u2:\n",
    "                ans |= ((1 ^ t) << i)\n",
    "            else:\n",
    "                ans |= (t << i)\n",
    "                t = 0\n",
    "        if ans & MASK2:  # 负数\n",
    "            return ~((ans ^ MASK2) ^ MASK3)\n",
    "        else:  # 正数\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return sum([a,b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return sum([a,b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import ctypes\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        while b!=0:\n",
    "            carry= ctypes.c_uint32(a&b).value<<1\n",
    "            a^=b\n",
    "            b= ctypes.c_int32(carry).value\n",
    "        return a    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return a + b\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return a+b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSum(self, a: int, b: int) -> int:\n",
    "        return a + b\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
